We show that for every cubic graph G with sufficiently large girth thereexists a probability distribution on edge-cuts of G such that each edge is in arandomly chosen cut with probability at least 0.88672. This implies that Gcontains an edge-cut of size at least 1.33008n, where n is the number ofvertices of G, and has fractional cut covering number at most 1.127752. Thelower bound on the size of maximum edge-cut also applies to random cubicgraphs. Specifically, a random n-vertex cubic graph a.a.s. contains an edge cutof size 1.33008n.
展开▼
